<?php

  class tool_clustering{

    public static function get_corners($_array_points){
      $pt=reset($_array_points);
      $nb_dimensions=count($pt);
      $point_max=array();
      $point_min=array();
      foreach($_array_points as $id_point=>$point){
        foreach($point as $dimension=>$valeur){
          if(!isset($point_max[$dimension]))
            $point_max[$dimension]=$valeur;
          if(!isset($point_min[$dimension]))
            $point_min[$dimension]=$valeur;
          else{
            if($valeur<$point_min[$dimension])
              $point_min[$dimension]=$valeur;
            if($valeur>$point_max[$dimension])
              $point_max[$dimension]=$valeur; 
          }
        }
      }
      return array($point_min,$point_max);      
    }

    public static function get_pts_start($_pt_min,$_pt_max,$_n){
      $nb_dimensions=count($_pt_min);
      $array_g=array();
      for($i=0;$i<$_n;++$i){
        $coord=array();
        for($j=0;$j<$nb_dimensions;++$j){
          //$dist=abs($_pt_max[$j]-$_pts_min[$j]);
          $dist=0;
          $coord[$j]=rand($_pt_min[$j]-$dist,$_pt_max[$j]+$dist);
        }
        $array_g[]=$coord;
      }
      return $array_g;

    }

    public static function run_cluster($_array_g,$_array_pts){
      $nb_dim=count(reset($_array_g));
      $array_cluster=array();
      foreach($_array_pts as $id_pt=>$pt){
        $array_dist_g=array();
        foreach($_array_g as $id_g=>$g){          
//          $dist=tool_maths::minkowski_metric($pt,$g,2);
          $dist=tool_maths::minkowski_metric($pt,$g,$nb_dim);
          $array_dist_g[$id_g]=$dist;
          if(!isset($g_target)) $g_target=$id_g;
          elseif($dist<$array_dist_g[$g_target]) $g_target=$id_g;
        }
        $array_cluster[$g_target][]=$id_pt;
        unset($g_target);
      }
      return $array_cluster;
    }

    public static function get_barycentre($_array_pts){
      $nb_vals=count($_array_pts);
      $origine=reset($_array_pts);
      $array_vector=array();
      foreach($_array_pts as $pt){
        $vector=tool_maths::get_vector($origine,$pt);
        if(!isset($sum_vector)) $sum_vector=$vector;
        else $sum_vector=tool_maths::sum_vector($sum_vector,$vector);
      }
      tool_maths::div_vector($sum_vector,$nb_vals);
      $sum_vector=tool_maths::sum_vector($origine,$sum_vector);
      return $sum_vector; 
    }

    public static function sort_array_cluster(&$_array_cluster){
      ksort($_array_cluster);
      foreach($_array_cluster as $cluster) ksort($cluster);
    }

    public static function run_cluster_final($array_pts,$_nb_clusters=null){
      list($min,$max)=self::get_corners($array_pts);
/*
      foreach($min as $d=>$v){
        $v_max=$max[$d];
        $dist=abs($v_max-$v);
        $max[$d]+=$dist;
        $min[$d]-=$dist;
      }
*/
      if($_nb_clusters==null)
        $nb_clusters=round(log(count($array_pts)))+1;
      else
        $nb_clusters=$_nb_clusters;
      $array_barycentre=self::get_pts_start($min,$max,$nb_clusters);
      $cpt=0;
      while($cpt<10000){
        $array_cluster=self::run_cluster($array_barycentre,$array_pts);
        $array_barycentre=array();
        foreach($array_cluster as $id_cluster=>$cluster){
          $pts=array();
          foreach($cluster as $id_pt) $pts[$id_pt]=$array_pts[$id_pt];
          $array_barycentre[$id_cluster]=self::get_barycentre($pts);
        }
        self::sort_array_cluster($array_cluster);
        if($old_array_cluster==$array_cluster){
          return $array_cluster;
        }
        $old_array_cluster=$array_cluster;
        ++$cpt;
      }
      return $array_cluster;
    }

    public static function strongest_clusters($array_pts,$_i=100,$_nb_cluster=null){
      $dico_cluster=array();
      $cpt_cluster=array();
      for($i=0;$i<$_i;++$i){
        $array_cluster=self::run_cluster_final($array_pts,$_nb_cluster);
        foreach($array_cluster as $cluster){
          $str=implode($cluster,":");
          $dico_cluster[$str]++;
        }
      }
      asort($dico_cluster);
      return $dico_cluster;
    }

  }


?>
